\documentclass[11pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{geometry}
\usepackage{cite}
\usepackage{graphicx}
\usepackage{float}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}

\usepackage{color}
\definecolor{verde}{rgb}{0,0.5,0}

\usepackage{listings}

\lstset{
  language=Java,
  basicstyle=\ttfamily\small, 
  keywordstyle=\color{blue}, 
  stringstyle=\color{verde}, 
  commentstyle=\color{red}, 
  extendedchars=true, 
  showspaces=false, 
  showstringspaces=false, 
  numbers=left,
  numberstyle=\tiny,
  breaklines=true, 
  breakautoindent=true,
  frame=single, 
  captionpos=b,
  xleftmargin=0pt,
}

\geometry{hmargin={2cm,2cm},vmargin={3cm,3cm},bmargin=2cm}

\usepackage{indentfirst}
\usepackage{url}
\usepackage[usenames,dvipsnames]{xcolor}

\author{
Eduardo Gomes Espinosa \\ \vspace{0,2cm}
\texttt{\small \url{edududu05@hotmail.com}} \\
Guilherme Ferreira Ribeiro \\ \vspace{1cm}
\texttt{\small \url{guifrribeiro@gmail.com}} \\
Faculdade de Computação \\
Universidade Federal de Uberlândia \\
Campus Santa Mônica}

\title{Análise de Algoritmos - Projeto 2 - Programação Dinâmica}

\begin{document}

\maketitle

\begin{abstract}
Este projeto é o resultado do estudo do tema Programação Dinâmica, estudado na disciplina Análise de Algoritmos. O prolema que estudaremos neste projeto é o "Problema do Corte de Pano". Será apresentando um pseudo-código para resolver o problema discutido, assim como sua análise e complexidade.
\end{abstract}

%Índices automáticos de conteúdo
\tableofcontents

\chapter{Introdução}
Vamos considerar uma peça de pano retangular de largura X e comprimento Y, onde X e Y são números inteiros positivos. E uma lista com \textit{n} produtos que são fabricados com o pano. Para cada produto \textit{i} = 1,...,\textit{n} é necessário um pedaço de pano com dimensões $\textit{a}_i$ (largura) e $\textit{b}_i$ (comprimento) e o preço final de venda do produto é de $\textit{c}_i$. Os números $\textit{a}_i$, $\textit{b}_i$, $\textit{c}_i$ são inteiros positivos. Teremos uma máquina que pode cortar qualquer peça retangular X por Y em duas peças, fazendo um corte horizontalmente em H ou verticalmente em V.

\chapter{Análise do Problema do Corte de Panos}
O problema que será estudado aqui consiste no seguinte:
Dados os número inteiros positivos $\textit{X}, \textit{Y}, \textit{n}, \{\textit{ai}, \textit{bi}, \textit{ci}, |\textit{i} \in \{1,...,\textit{n}\}\} $, determinar a melhor sequência $\textit{C}_1$, $\textit{C}_2$,...,$\textit{C}_k$ onde cada $\textit{C}_j$ corresponde a um corte horizontal ou vertical, de modo que as peças cortadas correspondentes aos cortes $\textit{C}_1$, $\textit{C}_2,...,\textit{C}_k$ são suficientes para a fabricação de um produto da lista e que a soma dos valores de venda destes produtos é maximal. Supõe-se que é permitido fabricar diversas cópias de um mesmo produto.
Podemos ver que o problema aqui descrito, é bem semelhante ao problema da mochila. Podemos dizer que é o problema da mochila bi-dimensional, pois no caso da mochila, a mesma tem apenas o peso, no nosso problema, teremos comprimento e largura, ou seja, o problema aqui dependerá de duas variáveis. Enquanto os itens no problema da mochila têm pesos e valores, aqui teremos da mesma forma comprimento, largura e valor. Ou seja, percebemos aqui que o que deveremos trocar para analisar o nosso problema é o peso pelas duas variáveis em questão (comprimento e largura).
A versão deste problema permite repetições, ou seja, podemos inserir várias cópias de uma mesma peça. Para resolvermos tal problema, precisamos pensar nos subproblemas que existem. Pode-se pensar que é possível olhar para panos com medidas menores, de forma que $\textit{x }\leq$\textit{ X} e $\textit{y }\leq$\textit{ Y}. Com esta restrição, podemos escrever:
\textit{K(x,y)} = maior valor alcançado com um pano de medidas \textit{x}, \textit{y}. Levando em consideração que a máquina que realizará os cortes no pano, faz apenas um tipo de corte, ou horizontal, ou vertical, teremos duas situações possíveis: uma em que o corte será realizado na vertical, e uma situação onde o corte será realizado na horizontal. Quando tivermos a primeira situação, teremos o seguinte subproblema: \textit{K(x}$\textit{,y - y}_i)$.
Quando o corte for feito na horizontal, teremos a seguinte fórmula: $\textit{K(x - x}_i$\textit{,y)}
Vamos enxergar isto em forma de subproblema menor. Se a solução de \textit{K(x,y)} inclui o produto \textit{i}, então removendo este produto do nosso pano teremos uma solução ótima para $\textit{K(x - x}_i$$\textit{,y - y}_i)$. Em outras palavras, \textit{K(x,y)} é simplesmente $\textit{K(x - x}_i$$\textit{,y - y}_i)$ + $\textit{c}_i$, para algum \textit{i}. Como não sabemos quem é o \textit{i}, temos de tentar todas as possibilidades.

\begin{equation}
K(x,y) = \max_{i:x_i \leq x} \{K(x,y-y_i) + c_i\} se x_i \leq y_i \\
K(x,y) = \max_{i:x_i \leq x} \{K(x-x_i,y) + c_i\} se y_i \leq x_i
\end{equation}

Tendo isto em mente, vamos apresentar o pseudo-código no próximo capítulo.

\chapter{Pseudo-código para o Problema do Corte de Panos}
O pseudo-código para resolver o problema do corte é apresentado a seguir:
\lstinputlisting[language=Java, label=mod_minimoc, caption={Corte de Pano}]{../pseudoCodigo/pseudo.txt}

\section{Análise do Algoritmo}
A complexidade esperada para este algoritmo é O(\textit{nXY}). Vamos analisar o algoritmo e provar esta complexidade. Temos na linha 1 apenas a inicialização do algoritmo, ou seja, o valor ótimo para uma peça de pano de largura 0 e comprimento também 0, será 0, e não teremos produtos a serem retornados.
Nas linhas 2 e 3 temos os "For", que serão responsáveis por percorrer as opções de peças de panos que teremos como subproblemas. Nas próximas linha temos as condições onde verificamos qual a melhor opção de corte (horizontal ou vertical). Tais testes têm complexidade \textit{O(1)}, assim como seus escopos. No fim temos apenas o retorno do algoritmo, que também tem complexidade \textit{O(1)}. Como temos um "for" dentro de outro,  sendo que o mais interno é executado \textit{O(Y)}, e o mais externo \textit{O(X)}, logo este algoritmo preenche uma tabela bi-dimensional de tamanho \textit{(X+1)}x\textit{(Y+1)}. Como cada chamada leva um tempo fixo de \textit{O(n)}, e temos que fazer \textit{XY} chamadas, chegamos num custo total de \textit{O(nXY)}.

\section{Testando o algoritmo}


\chapter{Implementação do Algoritmo}
Vamos usar a lnguagem Java para fazer a implementação do algoritmo proposto neste trabalho. A seguir teremos todas as classes e os métodos responsáveis por resolver o problema do corte de pano.

%\lstinputlisting[language=Java, label=mod_minimoc, caption={Classe Vertice}]{../Vertice.java}
%\lstinputlisting[language=Java, label=mod_minimoc, caption={Classe Aresta}]{../Aresta.java}
%\lstinputlisting[language=Java, label=mod_minimoc, caption={Classe Dijkstra}]{../Dijkstra.java}

\subsection{Exemplo de Execução}

%\lstinputlisting[language=Java, label=mod_minimoc, caption={Saida no grafo dado}]{../saida.txt}


\end{document}
